|
Completely Fair Scheduler (CFS) は、Linuxカーネル 2.6.23 にマージされたタスクスケジューラである。プロセス実行に必要なCPUリソース割り当てを行い、全体としてCPU利用効率を最大化しつつ対話的性能も最大化する。 のCPUスケジューリングに関する業績、特に Rotating Staircase Deadline と名付けたの実装に強く影響され、が従来のの代替としてCFSを開発した。 それまでの Linux 2.6 カーネルで使われていたとは対照的に、CFSスケジューラの実装はを採用していない。代わりに赤黒木で将来のタスク実行の予定表を実装している。さらにこのスケジューラはナノ秒単位の実行時間計測を行い、ナノ秒単位で個々のプロセスにCPUを割り当てる（したがって、それまでのタイムスライスの観念より細かい）。このように正確な知識を使うことで例えば、プロセスが対話的か否かを判定するのに特別なヒューリスティクスを使う必要がなくなる。 従来のO(1)スケジューラと同様、CFSは "sleeper fairness" という概念を採用している。これは、スリープまたはウェイトしているタスクとランキュー上で待っているタスクを公平に扱うという方針である。したがって時間の大部分をユーザーの入力などのイベントを待つことに費やしている対話型タスクであっても、必要ならそれなりのCPU時間を得ることができる。 == アルゴリズム == このスケジューラはタスク実行計画を赤黒木に記録しており、各タスクはそれまでに消費したプロセッサ時間をキーとして赤黒木に入れられる〔Linux カーネル 2.6 Completely Fair Scheduler の内側 ibm.com〕。それにより、消費したCPU時間が最も短いプロセスが効率的に選択できる（木の左端ノードに格納されている）。選択したプロセスを木から除去し、実行後は実行時間を更新して木構造上の適切な位置（通常は前とは別の位置）に戻す。そして新たな木の左端ノードを選択し、同様に繰り返す。 タスクが長時間スリープしている場合、実行時間の値が小さいため、スリープ状態から起きてきたときに自動的に優先度が上がる。したがってそのようなプロセスに割り当てられるプロセッサ時間が定常的に動作しているタスクより小さくなることはない。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Completely Fair Scheduler」の詳細全文を読む スポンサード リンク
|